package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

import java.util.*;

/**
 * 从上到下打印二叉树 |||
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9832%20-%20III.%20%E4%BB%8E%E4%B8%8A%E5%88%B0%E4%B8%8B%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91%20III/README
 */
public class P32_3 {

    public static void main(String[] args) {
        TreeNode nod1 = new TreeNode(3);
        TreeNode nod2 = new TreeNode(9);
        TreeNode nod3 = new TreeNode(20);
        TreeNode nod4 = new TreeNode(8);
        TreeNode nod5 = new TreeNode(6);
        TreeNode nod6 = new TreeNode(15);
        TreeNode nod7 = new TreeNode(7);
        TreeNode nod8 = new TreeNode(90);
        TreeNode nod9 = new TreeNode(67);
        nod1.left = nod2;
        nod1.right = nod3;
        nod2.left = nod4;
        nod2.right = nod5;
        nod3.left = nod6;
        nod3.right = nod7;
        nod6.left = nod8;
        nod6.right = nod9;
        Solution solution = new P32_3().new Solution();
        List<List<Integer>> lists = solution.levelOrder(nod1);
        for (int i = 0; i < lists.size(); i++) {
            for (int j = 0; j < lists.get(i).size(); j++) {
                System.out.print(lists.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            if (root == null) {
                return Collections.emptyList();
            }
            Deque<TreeNode> queue = new ArrayDeque<>();
            List<List<Integer>> list = new ArrayList<>();
            boolean flag = false;
            queue.offer(root);
            while(!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> t = new ArrayList<>();
                while (size -- >0) {
                    TreeNode node = queue.poll();
                    t.add(node.value);
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }

                }
                if (flag) {
                    Collections.reverse(t);
                }
                list.add(t);
                flag = !flag;
            }
            return list;
        }
    }
}
